package offer;
//二叉搜索树的后序遍历序列
public class T24 {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if (sequence.length<=0) return false;
        return BST(sequence,0,sequence.length-1);
    }
    public boolean  BST(int[] sequence,int l,int r) {
        if (l>=r) return true;
        int t = sequence[r];
        int mid = 0;
        for (int i = r-1; i >= l; i-- ) {
            if (sequence[i]<t) {
                mid = i + 1;
                break;
            }
        }
        for (int i = l; i < mid; i++) {
            if (sequence[i]>t) return false;
        }


        return  BST(sequence,l,mid-1)&&BST(sequence,mid,r-1);
    }
    public static void main ( String[] args) {

        System.out.println(new T24().VerifySquenceOfBST(new int[]{5,4,3,2,1}));
    }
}
